In a computer system, information is typically stored on a non-volatile storage device, such as a hard disk drive or solid-state disk, and cataloged in some hierarchical fashion so that the same information is more easily retrieved when desired. A unique code name, such as a file's name, is attributed to a particular body of data to differentiate it from others, and the desired body of data is retrievable via the use of the appropriate code name associated with that data. The device can search for that code name and retrieve the desired data when that code name is found. Typically, code names associated with particular data contain pointers, which point to areas in memory reserved for mass storage. The various code names and their pointers comprise a cataloging system used to order the data on the mass storage device. In the case of particularly high-density storage devices, multiple trillions of bytes of information can be stored on such devices.
One tool used to manage a complex hierarchical file system is an ordered tree data structure, such as a B-tree data structure. The B-tree data structure is well-known in the prior art and is described in The Art of Computer Programming Volume 3 2nd ed. (Sorting and Searching); by Donald E. Knuth; at §6.2.4; titled “Multiway Trees”; pp. 481-491 (1998). The nodes of a B-tree contain records; each record is comprised of certain information, such as metadata for data stored in a hierarchical file system. Each record also has a key associated with that record. In some B-tree variants, records are stored in leaf nodes of the tree, and keys are stored in index nodes.
Enabling multiple concurrent accesses to a B-tree file system structure can present particular problems. Early B-tree concurrency techniques focused on allowing concurrent access to the tree from multiple users, processes or threads without corrupting data within the tree. Additional techniques arose to avoid broken tree states that can result in a file-system malfunction. For example, if concurrent access is not properly managed, two or more threads can enter a deadlock state, where each thread is blocked from execution while waiting for a resource held by another blocked threaded. While simple concurrent access methods can provide stable storage for file system metadata, that stability comes largely as a result of serializing access to file system structures.